#include <iostream>
#include <vector>

int maxProfit(std::vector<int> weights, std::vector<int> profits, int max_weights)
{
    std::vector<std::vector<int>> dp(weights.size(), std::vector<int>(max_weights+1));

    for(int i = 0; i <= max_weights; i++)
    {
        if(i >= weights[0])
            dp[0][i] = profits[0];
    }

    for(int i = 1; i < weights.size(); i++)
    {
        for(int j = 1; j <= max_weights; j++)
        {
            if(j < weights[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = std::max(dp[i-1][j-weights[i]]+profits[i], dp[i-1][j]);
        }
    }

    return dp[weights.size()-1][max_weights];
}

int main()
{
    std::vector<int> weights = {2,5,1,2};
    std::vector<int> profits = {4,1,4,2};

    std::cout << maxProfit(weights, profits, 5) << std::endl;

    return 0;
}